//给你一个下标从 0 开始的二维数组 variables ，其中 variables[i] = [ai, bi, ci, mi]，以及一个整数 target 
//。 
//
// 如果满足以下公式，则下标 i 是 好下标： 
//
// 
// 0 <= i < variables.length 
// ((aibi % 10)ci) % mi == target 
// 
//
// 返回一个由 好下标 组成的数组，顺序不限 。 
//
// 
//
// 示例 1： 
//
// 
//输入：variables = [[2,3,3,10],[3,3,3,1],[6,1,1,4]], target = 2
//输出：[0,2]
//解释：对于 variables 数组中的每个下标 i ：
//1) 对于下标 0 ，variables[0] = [2,3,3,10] ，(2³ % 10)³ % 10 = 2 。
//2) 对于下标 1 ，variables[1] = [3,3,3,1] ，(3³ % 10)³ % 1 = 0 。
//3) 对于下标 2 ，variables[2] = [6,1,1,4] ，(6¹ % 10)¹ % 4 = 2 。
//因此，返回 [0,2] 作为答案。
// 
//
// 示例 2： 
//
// 
//输入：variables = [[39,3,1000,1000]], target = 17
//输出：[]
//解释：对于 variables 数组中的每个下标 i ：
//1) 对于下标 0 ，variables[0] = [39,3,1000,1000] ，(39³ % 10)¹⁰⁰⁰ % 1000 = 1 。
//因此，返回 [] 作为答案。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= variables.length <= 100 
// variables[i] == [ai, bi, ci, mi] 
// 1 <= ai, bi, ci, mi <= 10³ 
// 0 <= target <= 10³ 
// 
//
// Related Topics 数组 数学 模拟 👍 23 👎 0


package LeetCode.editor.cn;


import java.util.ArrayList;
import java.util.List;

/**
 * @author ldltd
 * @date 2024-07-30 15:54:44
 * @description 2961.双模幂运算
 
 */
 
public class DoubleModularExponentiation {
    public static void main(String[] args) {
    //测试代码
    DoubleModularExponentiation fun = new DoubleModularExponentiation();
    Solution solution= fun.new Solution();
        System.out.println(solution.helper(31,12,21,24));
        System.out.println(solution.fastP(2,3,5));
        System.out.println(8%5);
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    /*
    * 同余定理核心口诀：余同取余，和同加和，差同减差，最小公倍数作周期。

    余同：“一个数除以4余1，除以5余1，除以6余1”，则取1，表示为60+1。

    和同：“一个数除以4余3，除以5余2，除以6余1”，则取7，表示为60+7。

    差同：“一个数除以4余1，除以5余2，除以6余3”，则取-3，表示为60-3。

    (a-b)%m=c  则 a%m=c b%m=c  即同余

    四个数 若ab同余、cd同余，那么ac与bd同余

    (a⋅b)%m=[(a%m)⋅(b%m)]%m

    * */
    public List<Integer> getGoodIndices(int[][] variables, int target) {
        List<Integer> res=new ArrayList<>();
        for (int i=0;i<variables.length;i++) {
            if(helper(variables[i][0],variables[i][1],variables[i][2],variables[i][3] )==target)
                res.add(i);
        }
        return res;
    }
    public int helper(int a, int b, int c, int m){

       return (int) fastPow(fastPow(a,b,10),c,m);
    }
    public  int fastPow(int a,int b,int c){
        int res=1;
        if(b<0){
            b=-b;
            a=1/a;
        }
        while (b!=0){
            if((b&1)==1){
                res=res*a%c;
            }
            a=a*a%c;
            b>>=1;
        }
        return res;
    }

    public  int fastP(int a,int b, int c){
        if(b<0){
            b=-b;
            a=1/a;
        }
        int res=1;
        while (b!=0){
            if((b&1)==1){
                res=res*a%c;
            }
            a=a*a%c;
            b>>=1;
        }
        return res;
    }


}
//leetcode submit region end(Prohibit modification and deletion)

}
